package cn.dapeng.other;

/**
 * @BelongProject study
 * @BelongPackage cn.dapeng.other
 * @Description 斐波那契数列
 * @ClassName Fibonacci
 * @Author xupenghong
 * @Date 2024/8/20 16:16
 * @Version 1.0.0
 */
public class Fibonacci {

    /**
     * 效率最低
     * @param n
     * @return
     */
    public static long fibo1(int n) {
        if (n < 0) {
            return 0;
        }

        if (n == 0 || n == 1) {
            return 1;
        }
        return fibo1(n - 1) + fibo1(n - 2);
    }

    /**
     * 效率最高
     * @param n
     * @return
     */
    public static long fibo2(int n) {
        if (n < 0) {
            return 0;
        }

        if (n == 0 || n == 1) {
            return 1;
        }

        long first = 1, second = 1;
        for (int i = 2; i <= n; i++) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

    /**
     * 效率最高
     * @param n
     * @return
     */
    public static long fibo3(int n) {
        if (n < 0) {
            return 0;
        }

        if (n == 0 || n == 1) {
            return 1;
        }

        long[] array = new long[2];
        array[0] = 1;
        array[1] = 1;
        for (int i = 2; i <= n; i++) {
            array[1] = array[0] + array[1];
            array[0] = array[1] - array[0];
        }
        return array[1];
    }

    /**
     * 通过构建一个数组， 空间复杂度太高
     * @param n
     * @return
     */
    public static long fibo4(int n) {
        if (n < 0) {
            return 0;
        }

        if (n == 0 || n == 1) {
            return 1;
        }

        long[] array = new long[n + 1];
        array[0] = 1;
        array[1] = 1;
        array[2] = 2;

        for (int i = 3; i <= n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }
    public static void main(String[] args) {
        //System.out.println(fibo1(50));
        System.out.println(fibo2(51));
        System.out.println(fibo3(51));
        System.out.println(fibo4(51));
    }
}
